/*
Source : https://leetcode.com/problems/surrounded-regions/
Author : nflush@outlook.com
Date   : 2016-07-07
*/

/*
130. Surrounded Regions

    Total Accepted: 56800
    Total Submissions: 344997
    Difficulty: Medium

Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

For example,

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

Subscribe to see which companies asked this question
*/

class Solution {
typedef struct node_t{
    int h;
    int s;
    int e;
    struct node_t *sub;
    int subIndex;
    struct node_t *child;
    int childIndex;
    bool edge;
    bool disable;
}node;
    bool bisCross(const node_t *a,const node_t *b){
        if (a->s <= b->s&&a->e >= b->s){
            return true;
        }
        if (b->s <= a->s && b->e >= a->s){
            return true;
        }
        if (b->sub) return bisCross(a, b->sub);
        return false;
    }
    int countNode(vector<char>&cow, vector<node>&land, int h){
        bool inNode = false;
        node one = {h, 0, 0, NULL, 0};
        for (int i =0; i < cow.size(); i++){
            if (cow[i] == 'O'){
                if (!inNode){
                    inNode = true;
                    one.s = i;
                }
            } else {
                if (inNode){
                    inNode = false;
                    one.e = i-1;
                    one.edge = (h==0 || one.s==0);
                    land.push_back(one);
                }
            }
        }
        if (inNode){
            one.e = cow.size() -1;
            one.edge = true;
            land.push_back(one);
        }
        return land.size();
    }
    void clearNode(vector<vector<char>>& board, node &n , vector<node> &pre){
        for (int i = n.s; i <= n.e; i++){
            board[n.h][i] = 'X';
        }
        if (n.subIndex){
            clearNode(board, pre[n.subIndex-1], pre);
        }
        if (n.childIndex){
            return clearNode(board, pre[n.childIndex-1], pre);
        }
    }
public:
    void solve(vector<vector<char>>& board) {
        vector<node> pre;
        vector<node> land[2];
        int index = 0;

        for (int i =0; i < board.size(); i++, index ^= 1){
            land[index].clear();
            int count = countNode(board[i], land[index], i);
            if (count){
                int total = count;
                for(int j = 0;j < land[index^1].size(); j++){
                    if (land[index^1][j].disable) continue;
                    node *LN = NULL;
                    node &LO = land[index^1][j];

                    for (int k = 0; k < total; k++){
                        if (bisCross(&land[index][k], &LO)){
                            land[index][k].edge |= LO.edge;
                            LO.edge |= land[index][k].edge;
                            if (!LN){
                                LN = &land[index][k];
                            } else {
                                land[index][k].sub = LN->sub;
                                LN->sub = &land[index][k];
                                land[index][k].disable = true;
                                LN->edge |= LO.edge;
                            }
                        }
                    }
                    if (LN) { // has cross
                        if (LO.edge) continue;
                        pre.push_back(LO);
                        if (LN->childIndex){
                            int sub = LN->childIndex;
                            for (;pre[sub-1].subIndex != 0; sub = pre[sub-1].subIndex);
                            pre[sub-1].subIndex = pre.size();
                        } else 
                            LN->childIndex = pre.size();
                        while (LO.sub){
                            pre.push_back(*LO.sub);
                            pre[pre.size()-2].subIndex = pre.size();
                            LO = *LO.sub;
                        }
                    } else {
                        if (!LO.edge){
                            clearNode(board, LO, pre);
                        }
                    }
                }
            }else {
                for (auto &n : pre){
                    if (!n.edge){
                        clearNode(board, n, pre);
                    }
                }
                for (auto &n:land[index^1]){
                    if (!n.edge){
                        clearNode(board, n, pre);
                    }
                }
                pre.clear();
            }
        }
    }
};

